﻿#pragma once
#include <assert.h>

namespace bit
{
	template <class T>
	struct list_node
	{
		T _data;
		list_node* _prev;
		list_node* _next;
		//const int a = int();
		list_node(const T dat = T())
			:_data(dat)
			,_prev(nullptr)
			,_next(nullptr)
		{ }
	};

	//typedef _literal<T, T&, T*> iterator;
	//typedef _literal<T, const T&, const T*> const_iterator;
	template <class T,class Ref,class Ptr>
	struct _literal
	{
		typedef list_node<T> Node;
		typedef _literal<T,Ref,Ptr> self;
		Node* _node;

		_literal(Node* node)
			:_node(node)
		{ }

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}
		//++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		bool operator!=(const self& it)
		{
			return (_node != it._node);
		}

		bool operator==(const self& it)
		{
			return (_node == it._node);
		}
	};

	template <class T>
	class list
	{
	public:
		typedef list_node<T> Node;
		typedef _literal<T,T&,T*> iterator;
		typedef _literal<T,const T&,const T*> const_iterator;

		////✅ 推荐使用 new Node()，因为它能保证正确初始化，避免未定义行为。
		////	❌ new Node 在某些情况下可能导致未初始化的成员变量（危险！）。
		list()
		{
			_head = new Node();//_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		//list(const list<T>& lt)
		//{
		//	_head = new Node();
		//	_head->_next = _head;
		//	_head->_prev = _head;
		//	
		//	for (auto e : lt)
		//	{
		//		push_back(e);
		//	}
		//}

		//void operator=(list<T> lt)
		//{
		//	swap(_head, lt._head);
		//}

		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		template <class InputItretor>
		list(InputItretor first,InputItretor last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		list(const list<T>& lt)
		{
			empty_init();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		void push_back(const T& x)
		{
			//Node* tmp = new Node();
			//Node* tail = _head->_prev;
			//tmp->_data = x;

			//tail->_next = tmp;
			//tmp->_prev = tail;
			//_head->_prev = tmp;
			//tmp->_next = _head;

			insert(end(), x);
		}

		void push_front(const T& x)
		{
			//Node* tmp = new Node();
			//Node* head = _head->_next;
			//tmp->_data = x;

			//_head->_next = tmp;
			//tmp->_prev = _head;
			//tmp->_next = head;
			//head->_prev = tmp;

			insert(begin(), x);
		}

		void pop_front(void)
		{
			assert(_head != _head->_next);
			//Node* tmp = _head->_next;
			//Node* newhead = tmp->_next;
			//delete tmp;
			//tmp = nullptr;
			//_head->_next = newhead;
			//newhead->_prev = _head;

			erase(begin());
		}

		void pop_back(void)
		{
			//assert(_head != _head->_next);
			//Node* tmp = _head->_prev;
			//Node* newtail = tmp->_prev;
			//delete tmp;
			//tmp = nullptr;
			//_head->_prev = newtail;
			//newtail->_next = _head;

			erase(--end());
		}

		void insert(iterator it, const T& x)
		{
			Node* pos = it._node;
			Node* newnode = new Node(x);
			Node* pospre = pos->_prev;

			pospre->_next = newnode;
			newnode->_prev = pospre;
			newnode->_next = pos;
			pos->_prev = newnode;

		}
		//lt.erase(it1)
		iterator erase(iterator it)
		{
			//assert(_head != it._node);
			assert(it != end());

			Node* pos = it._node;

			Node* pospre = pos->_prev;
			Node* posnex = pos->_next;

			//delete pos;
			//pos = nullptr;

			pospre->_next = posnex;
			posnex->_prev = pospre;
			delete pos;

			return iterator(posnex);
		}

		void clear(void)
		{
			//Node* cur = _head->_next;
			//while (_head != cur)
			//{
			//	Node* next = cur->_next;
			//	_head->_next = next;
			//	next->_prev = _head;
			//	delete cur;
			//	cur = next;
			//}

			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

	private:
		Node* _head;
	};

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it = 10; // 不允许修改
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void test_list1(void)
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	struct AA
	{
		AA(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{
		}

		int _a1;
		int _a2;
	};

	void test_list2()
	{
		list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));
		lt.push_back(AA(4, 4));

		// 迭代器模拟的是指针行为
		// int* it  *it
		// AA*  it  *it  it->
		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it)._a1 << "-"<< (*it)._a2 <<" ";
			//cout << it->_a1 << "-" << it->_a2 << " ";
			++it;
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		lt.push_front(1);
		lt.push_front(2);
		lt.push_front(3);
		lt.push_front(4);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_front();
		lt.pop_front();

		lt.pop_back();
		//lt.pop_back();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list4()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);

		// 要求在偶数的前面插入这个偶数*10
		auto it1 = lt.begin();
		while (it1 != lt.end())
		{
			if (*it1 % 2 == 0)
			{
				lt.insert(it1, *it1 * 10);
			}

			++it1;
		}

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list5()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);

		auto it1 = lt.begin();
		while (it1 != lt.end())
		{
			if (*it1 % 2 == 0)
			{
				it1 = lt.erase(it1);
			}
			else
			{
				++it1;
			}
		}

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.clear();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list6()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);

		list<int> lt1(lt);

		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt2;
		lt2.push_back(10);
		lt2.push_back(20);
		lt1 = lt2;
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}